package algorithms.bloom;

import java.nio.charset.Charset;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;

/**
 * Implementation of a Bloom-filter, as described here:
 * http://en.wikipedia.org/wiki/Bloom_filter * Source:
 * http://java-bloomfilter.googlecode.com
 * 
 * @author Magnus Skjegstad <magnus@skjegstad.com>
 */
public class BloomFilter<E> {
	private static final long serialVersionUID = 1L;
	private BitSet _bitset; // bit array
	private int _m; // length of the bit array
	private int _n; // expected (maximum) number of elements to be added
	private int _noOfAddedElements; // number of elements actually added to the
									// Bloom filter
	private int _k; // number of hash functions
	static final Charset charset = Charset.forName("UTF-8"); // encoding used
																// for storing
																// hash values
																// as strings
	static final String hashName = "MD5"; // MD5 gives good enough accuracy in
											// most circumstances. Change to
											// SHA1 if it's needed
	static final MessageDigest hashFunction;
	static { // The digest method is reused between instances
		MessageDigest tmp;
		try {
			tmp = java.security.MessageDigest.getInstance(hashName);
		} catch (NoSuchAlgorithmException e) {
			tmp = null;
		}
		hashFunction = tmp;
	}

	/**
	 * Constructs an empty Bloom filter. The total length of the Bloom filter
	 * will be c*n.
	 * 
	 * @param m
	 *            is the number of bits in the bitset.
	 * @param n
	 *            is the expected number of elements the filter will contain.
	 * @param k
	 *            is the number of hash functions used.
	 */
	public BloomFilter(int m, int n, int k) {
		_n = n;
		_k = k;
		_m = m; // the length of the bitarray
		_noOfAddedElements = 0;
		_bitset = new BitSet(_m);
	}

	// USES BLOOM FILTER LOAD FACTOR
	/**
	 * Constructs an empty Bloom filter. The optimal number of hash functions
	 * (k) is estimated from the total size of the Bloom and the number of
	 * expected elements.
	 * 
	 * @param m
	 *            - bitSetSize defines how many bits should be used in total for
	 *            the filter.
	 * @param n
	 *            - expectedNumberOfElements defines the maximum number of
	 *            elements the filter is expected to contain.
	 */
	public BloomFilter(int m, int n) {
		// call first constructor
		this(m, n, (int) Math.round(((double) m / (double) n) * Math.log(2.0))); // k
																					// =
																					// m/n
																					// *
																					// ln2
	}

	/**
	 * Generates digests based on the contents of an array of bytes and splits
	 * the result into 4-byte int's and store them in an array. The digest
	 * function is called until the required number of int's are produced. For
	 * each call to digest a salt is prepended to the data. The salt is
	 * increased by 1 for each call.
	 * 
	 * @param data
	 *            specifies input data.
	 * @param hashes
	 *            number of hashes/int's to produce.
	 * @return array of int-sized hashes
	 */
	public static int[] createHashes(byte[] data, int noOfHashFuncs) {
		int[] result = new int[noOfHashFuncs];
		int k = 0;
		byte salt = 0; // used to make each hash function different
		while (k < noOfHashFuncs) {
			byte[] hashValue; // the array of bytes for the resulting hash value
			synchronized (hashFunction) {
				hashFunction.update(salt);
				salt++;
				hashValue = hashFunction.digest(data); // computes the hash
														// value (array of
														// bytes)
			}
			for (int i = 0; i < hashValue.length / 4 && k < noOfHashFuncs; i++) {
				int h = 0;
				for (int j = (i * 4); j < (i * 4) + 4; j++) {
					h <<= 8;
					h |= ((int) hashValue[j]) & 0xFF;
				}
				result[k] = h;
				k++;
			}
		}
		return result;
	}

	/**
	 * Calculates the expected probability of false positives based on the
	 * number of expected filter elements and the size of the Bloom filter. <br />
	 * <br />
	 * The value returned by this method is the <i>expected</i> rate of false
	 * positives, assuming the number of inserted elements equals the number of
	 * expected elements. If the number of elements in the Bloom filter is less
	 * than the expected value, the true probability of false positives will be
	 * lower.
	 * 
	 * @return expected probability of false positives.
	 */
	public double expectedFalsePositiveProbability() {
		return getFalsePositiveProbability(_n);
	}

	/**
	 * Calculate the probability of a false positive given the specified number
	 * of inserted elements.
	 * 
	 * @param numberOfElements
	 *            number of inserted elements.
	 * @return probability of a false positive.
	 */
	public double getFalsePositiveProbability(double noOfElements) {
		// (1 - e^(-k * n / m)) ^ k
		return Math.pow(
				(1 - Math.exp(-1 * _k * (double) noOfElements / (double) _m)),
				_k);
	}

	/**
	 * Get the current probability of a false positive. The probability is
	 * calculated from the size of the Bloom filter and the current number of
	 * elements added to it.
	 * 
	 * @return probability of false positives.
	 */
	public double getFalsePositiveProbability() {
		return getFalsePositiveProbability(_noOfAddedElements);
	}

	/**
	 * Returns the value chosen for K.<br />
	 * <br />
	 * K is the optimal number of hash functions based on the size of the Bloom
	 * filter and the expected number of inserted elements.
	 * 
	 * @return optimal k.
	 */
	public int getK() {
		return _k;
	}

	/**
	 * Sets all bits to false in the Bloom filter.
	 */
	public void clear() {
		_bitset.clear();
		_noOfAddedElements = 0;
	}

	/**
	 * Adds an object to the Bloom filter. The output from the object's
	 * toString() method is used as input to the hash functions.
	 * 
	 * @param element
	 *            is an element to register in the Bloom filter.
	 */
	public void add(E element) {
		// add the element to the Bloom filter
		add(element.toString().getBytes(charset));
	}

	/**
	 * Adds an array of bytes to the Bloom filter.
	 * 
	 * @param bytes
	 *            array of bytes to add to the Bloom filter.
	 */
	private void add(byte[] bytes) {
		// create hashes of the bytes
		int[] hashes = createHashes(bytes, _k);
		// set the appropriate index in the bitArray to true
		for (int hash : hashes) {
			_bitset.set(Math.abs(hash % _m), true);
		}
		// increase the number of added elements
		_noOfAddedElements++;
	}

	/**
	 * Returns true if the element could have been inserted into the Bloom
	 * filter. Use getFalsePositiveProbability() to calculate the probability of
	 * this being correct.
	 * 
	 * @param element
	 *            element to check.
	 * @return true if the element could have been inserted into the Bloom
	 *         filter.
	 */
	public boolean contains(E element) {
		return contains(element.toString().getBytes(charset));
	}

	/**
	 * Returns true if the array of bytes could have been inserted into the
	 * Bloom filter. Use getFalsePositiveProbability() to calculate the
	 * probability of this being correct.
	 * 
	 * @param bytes
	 *            array of bytes to check.
	 * @return true if the array could have been inserted into the Bloom filter.
	 */
	private boolean contains(byte[] bytes) {
		int[] hashes = createHashes(bytes, _k);
		for (int hash : hashes) {
			if (!_bitset.get(Math.abs(hash % _m)))
				return false;
		}
		return true;
	}

	/**
	 * Return the bit set used to store the Bloom filter.
	 * 
	 * @return bit set representing the Bloom filter.
	 */
	public BitSet getBitSet() {
		return _bitset;
	}

	/**
	 * Returns the number of bits in the Bloom filter. Use count() to retrieve
	 * the number of inserted elements.
	 * 
	 * @return the size of the bitset used by the Bloom filter.
	 */
	public int size() {
		return _m;
	}

	/**
	 * Returns the number of elements added to the Bloom filter after it was
	 * constructed or after clear() was called.
	 * 
	 * @return number of elements added to the Bloom filter.
	 */
	public int count() {
		return this._noOfAddedElements;
	}

	/**
	 * Returns the expected number of elements to be inserted into the filter.
	 * This value is the same value as the one passed to the constructor.
	 * 
	 * @return expected number of elements.
	 */
	public int getExpectedNumberOfElements() {
		return _n;
	}
}